home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 126-150 / disk_138 / amigaline / amigaline6 < prev    next >
Text File  |  1992-05-06  |  3KB  |  91 lines
  1.             Technical Note #6
  2.         How to calulate the AmigaDOS hash function
  3.  
  4. SUMMARY
  5.  
  6. $ 6/0 How to calulate the AmigaDOS hash function
  7. $ release 2
  8. $ 20-Jan-88 Bryce Nesbitt (from Neil Katin) / BDI (Commodore-Amiga Inc.)
  9. $ AmigaDOS, disk, directory, hash function, directory block, file system
  10.  
  11.     AmigaDOS uses a hashed directory structure for very rapid finding of a
  12. file (given the complete path name).  This note gives a function to find the
  13. hash value of a name.
  14.  
  15. ----------------------------------------------------------------------------
  16.  
  17. /* hasher.c - By Bryce Nesbitt
  18.  
  19.     Calulates hash values.
  20.  
  21.     In order to find a particlar file, AmigaDOS applies the hash function
  22. to the filename.  The resulting value is looked up in the hash table for a
  23. particular directory.  Zero at this location indicates the file does not
  24. exist.    A non-zero number is a key for a block.  This will either be the
  25. proper file, or one in a chain of names which all have the same hash value.
  26. See the AmigaDOS Technical Reference Manual for more deails.
  27.  
  28.     Remember that these hash functions will be valid ONLY for filesystems
  29. of type "DOS\0".  This file system identifier is stored in the first long
  30. of the boot block.
  31.  
  32.     The size of the hash table for a particular file is stored in a long
  33. word at offset $C (12) in the root block.  Normally with 90mm disks this
  34. will indicate that the table has $48 (72) entires.
  35.  
  36.  
  37.     This example was based on examples by Neil Katin (pyramid!amiga!neil)
  38. and Carolyn Scheppner ({allegra,ihnp4,rutgers}!cbmvax!carolyn).
  39. */
  40.  
  41. typedef unsigned short USHORT;
  42. /* Remove if duplicated elsewhere */
  43.  
  44. USHORT HashString(unsigned char *,USHORT);
  45. /* For old compilers use "USORT HashString();" */
  46.  
  47.  
  48. void main( argc, argv )
  49. int  argc;
  50. char *argv[];
  51. {
  52. USHORT hashoffset;
  53.  
  54.     if( argc != 2 ) {
  55.     printf("Calulates the offset into a 72 entry AmigaDOS hash table\n");
  56.     printf("Usage: %s <name>\n", argv[0] );
  57.     exit(5);
  58.     }
  59.     hashoffset=HashString( argv[1],72 );
  60.     /* Don't assume the hash table size will always be 72! */
  61.     printf( "Table entry is $%x (%d)\n", hashoffset, hashoffset );
  62.     printf( "Byte location in block is $%x (%d)\n", (hashoffset+6)<<2,
  63.     (hashoffset+6)<<2);
  64. }
  65.  
  66.  
  67.  
  68. USHORT HashString(string,tablesize)
  69. unsigned char  *string;
  70. USHORT tablesize;
  71. {
  72.     register unsigned char c;
  73.     register USHORT result;
  74.  
  75.  
  76.     result = strlen(string);
  77.  
  78.     while( c = *string ) {
  79.     if( c >= 'a' && c <= 'z' ) {    /* If lower case */
  80.         c = c - 'a'+'A';           /* Convert to upper */
  81.     }
  82.     result = (( result * 13 + c ) & 0x7ff);
  83.     string++;
  84.     }
  85.  
  86.     return( (USHORT)(result % tablesize) );
  87. }
  88.  
  89.  
  90.  
  91.